#https://zhuanlan.zhihu.com/p/60731708
def quick_sort(a_list):
    if len(a_list)<2:
        return a_list
    # choice pivot
    left =[]
    right =[]
    mid = a_list[len(a_list)//2]
    a_list.remove(mid)

    for item in a_list:
        if item >= mid:
            right.append(item)
        else:
            left.append(item)

    return quick_sort(left) + [mid] + quick_sort(right)

if __name__ == "__main__":
    a_list = [3,6,4,1,2,9,2]
    sorted_list = quick_sort(a_list) 
    print(sorted_list)    
    pass
